// n 皇后
var generateBoard = function (queens, n) {
  let board = []
  for (let i = 0; i < n; i++) {
    let row = new Array(n).fill('.')
    row[queens[i]] = 'Q'
    board.push(row.join(''))
  }
  return board
}
var dfs = function (
  solutions,
  queens,
  n,
  row,
  columns,
  diagonals1,
  diagonals2
) {
  if (row === n) {
    let board = generateBoard(queens, n)
    solutions.push(board)
  } else {
    for (let i = 0; i < n; i++) {
      if (columns.has(i)) continue
      if (diagonals1.has(row - i)) continue
      if (diagonals2.has(row + i)) continue
      queens[row] = i
      columns.add(i)
      diagonals1.add(row - i)
      diagonals2.add(row + i)
      dfs(solutions, queens, n, row + 1, columns, diagonals1, diagonals2)
      queens[row] = -1
      columns.delete(i)
      diagonals1.delete(row - i)
      diagonals2.delete(row + i)
    }
  }
}
var solveNQueens = function (n) {
  let solutions = []
  let queens = new Array(n).fill(-1)
  let columns = new Set()
  let diagonals1 = new Set()
  let diagonals2 = new Set()

  dfs(solutions, queens, n, 0, columns, diagonals1, diagonals2)
  return solutions
}

var r = solveNQueens(4)

console.log(r)
